#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++) 
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;

int read() {
	int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-', ch = getchar(); 
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return f ? -x : x;
}

const int N = 555;
const int mod = 1e9 + 7;

int fac[N], ifac[N], w, h, n, d, ans;
inline ll qp(ll x, int t) { ll res = 1; for(; t; t >>= 1, x = x * x % mod) if(t & 1) res = res * x % mod; return res; }
inline ll C(int x, int y) { return x < y || x < 0 || y < 0 ? 0 : 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod; }
int calc(int x, int y) {
	if(x == 0 && y == 0) return 0;
	int G = __gcd(x, y), D = ceil(d / sqrt((x / G) * (x / G) + (y / G) * (y / G)));
	ll res = C(G - (D - 1) * (n - 1) - 1, n - 2);
	if(x && y) res = res * 2 % mod;
	res = res * (w - x + 1) % mod * (h - y + 1) % mod;
	//	cerr << x << " " << y << " " << res << endl;
	return res;
}

void solve() {
	n = in, w = in, h = in, d = in; ans = 0;
	if(n == 1) ans = 1ll * (w + 1) * (h + 1) % mod;
	else
		rep(x, 0, w)
			rep(y, 0, h) ans = (ans + calc(x, y)) % mod;
	printf("%d\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	fac[0] = 1; rep(i, 1, 550) fac[i] = 1ll * fac[i - 1] * i % mod; ifac[550] = qp(fac[550], mod - 2);
	per(i, 549, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
	int T = in; while(T--) solve();
	return 0;
}
